package com.hspedu.newData.力扣周赛.周赛.第450;

import java.util.*;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-18 
 * @Version: 1.0
 */

public class Q3网络传送门旅游 {
    static class State {
        int x, y, steps, mask;
        State(int x, int y, int steps, int mask) {
            this.x = x;
            this.y = y;
            this.steps = steps;
            this.mask = mask;
        }
    }

    public static int minMoves(String[] matrix) {
        int m = matrix.length, n = matrix[0].length();
        char[][] grid = new char[m][n];
        Map<Character, List<int[]>> portalMap = new HashMap<>();

        // Step 1: 预处理 grid 和 portal 位置
        for (int i = 0; i < m; i++) {
            grid[i] = matrix[i].toCharArray();
            for (int j = 0; j < n; j++) {
                char ch = grid[i][j];
                if (ch >= 'A' && ch <= 'Z') {
                    portalMap.computeIfAbsent(ch, k -> new ArrayList<>()).add(new int[]{i, j});
                }
            }
        }

        // Step 2: 给实际使用的传送门编码（压缩 bit 位）
        Map<Character, Integer> portalBit = new HashMap<>();
        int portalCount = 0;
        for (char ch : portalMap.keySet()) {
            portalBit.put(ch, portalCount++);
        }

        // Step 3: 0-1 BFS 初始化
        Deque<State> deque = new ArrayDeque<>();
        boolean[][][] visited = new boolean[m][n][1 << portalCount];

        deque.offerFirst(new State(0, 0, 0, 0));
        visited[0][0][0] = true;

        int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};

        while (!deque.isEmpty()) {
            State cur = deque.pollFirst();
            int x = cur.x, y = cur.y, steps = cur.steps, mask = cur.mask;

            if (x == m - 1 && y == n - 1) return steps;

            // Step 4: 优先处理传送门（cost = 0）
            char ch = grid[x][y];
            if (portalBit.containsKey(ch)) {
                int bit = portalBit.get(ch);
                if ((mask & (1 << bit)) == 0) {
                    int newMask = mask | (1 << bit);
                    for (int[] pos : portalMap.get(ch)) {
                        int px = pos[0], py = pos[1];
                        if (px == x && py == y) continue;
                        if (!visited[px][py][newMask]) {
                            visited[px][py][newMask] = true;
                            deque.offerFirst(new State(px, py, steps, newMask));  // 放队头，优先处理
                        }
                    }
                }
            }

            // Step 5: 普通移动（cost = 1）
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && ny >= 0 && nx < m && ny < n && grid[nx][ny] != '#') {
                    if (!visited[nx][ny][mask]) {
                        visited[nx][ny][mask] = true;
                        deque.offerLast(new State(nx, ny, steps + 1, mask));  // 放队尾
                    }
                }
            }
        }

        return -1;
    }

    // 示例
    public static void main(String[] args) {
        String[] matrix = {
                "..C.",
                "C.A."
        };

        System.out.println("最少移动步数: " + minMoves(matrix));  // 输出应为合理的步数
    }

}
